# What is the first term in the Fibonacci sequence to contain 1000 digits?
# http://projecteuler.net/index.php?section=problems&id=25

from datetime import timedelta
from datetime import datetime
start = datetime.now()

index = 2
fib0 =  [1]
fib1 = [1]
r_fib0 = []
r_fib1 = []

while (len(fib1) < 1000):
    index = index + 1
    r_fib0[:] = fib0[:]
    r_fib0.reverse()
    r_fib1[:] = fib1[:]
    r_fib1.reverse()
    fib0[:] = fib1[:]
    fib1 = [0]
    while True:
        if len(r_fib1) != len(r_fib0):
            r_fib0.append(0);
        else:
            break
    for i in range(len(r_fib1)):
        total = r_fib0[i] + r_fib1[i]
        fib1[0] += total % 10
        if (total / 10):
            fib1.insert(0, total / 10)
        elif i != len(r_fib1) - 1:
            fib1.insert(0, 0)            
print index

timedelta = datetime.now() - start;
print "Performance: %fsecs" % timedelta.total_seconds()

            
            